package com.company.笔试.常用排序算法.快速排序;

import com.company.笔试.常用排序算法.array.ArrayData;

import java.util.Arrays;

/**
 * @ClassName Sulution
 * @Description TODO
 * @Author ylr
 * @Date 2021/7/20 18:23
 * @Version 1.0
 */
public class Solution {
    public static void main(String[] args) {
            System.out.println(Arrays.toString(quickSort(new ArrayData().getA())));

    }
    public static int[] quickSort(int[] arr){
        int length = arr.length;
        int left=0;
        int right=length-1;

        quickSortSolution(arr,left,right);


        return arr;
    }

    private static void quickSortSolution(int[] arr, int left, int right) {
        if (left>right) return;
        int mid = findMid(arr,left,right);
        quickSortSolution(arr,left,mid-1);
        quickSortSolution(arr,mid+1,right);

    }

    /**
     * 找到中间数的索引
     */
    private static int findMid(int[] arr, int left, int right) {
        /**
         * 中间数假定为左边的第一个
         */
        int midVal = arr[left];
        while (left<right){
            /**
             * 从右边开始找小于中间数 的数
             */
            while (left<right){
                if (arr[right]<midVal){
                    /**
                     * 在右边找到小于中间数的数
                     * 右边的覆盖左边的,因为左边第一个是中间数被保存了,可以放心覆盖
                     *
                     */
                    arr[left]=arr[right];
                    left++;
                    break;
                }
                right--;
            }
            /**
             * 从左边开始找大于中间的数
             * 然后把这个数放到右边索引
             */
            while (left<right){
                if (arr[left]>midVal){
                    arr[right]=arr[left];
                    right--;
                    break;
                }
                left++;
            }
        }
        /**
         * 一轮下来大于中间的在右边 小于中间的在左边
         */
        arr[left]=midVal;
        return left;


    }
}
